1. Technical Field
The present invention relates generally to a method for preventing overflow of arrays/buffers that are dynamically allocated on a stack and, in particular, to a method that allows a procedure, which is passed a stack allocated array/buffer as an argument, to determine a xe2x80x9csafexe2x80x9d upper bound on the size of the stack allocated array/buffer to thereby prevent back-chain and/or procedure return pointers from being overwritten due to overflow of the array/buffer.
2. Description of Related Art
Virtually all programs written in modern programming languages, such as C, C++ or Java, use a stack for maintaining a program stack while the program is running. A stack is a contiguous region of memory (comprising data items such as words, character, bits, etc.) that grows and shrinks based on the demands of the program. Typically, one end of this stack region (i.e., the bottom of the stack) is fixed at a predetermined address in memory, while the other end of the stack (i.e., the top of the stack) moves up/down to increase/decrease the amount of stack space available to the program. The program maintains what is known as a xe2x80x9cstack pointerxe2x80x9d that points the current position of the mutable end (i.e., the top of the stack). More specifically, the stack pointer is a either a register or memory word that contains the address of the top of the stack.
Programs execute by calling functions (or procedures or subroutines) which, in turn, may call other functions, etc. Each time a function is called, a block of memory called a xe2x80x9cstack framexe2x80x9d is allocated on the stack to accommodate the state of the called function, i.e., for storing parameters, a return address and local variable, if any, associated with the called function. The running program typically maintains a pointer to the start of the region, known as the xe2x80x9cframe pointerxe2x80x9d.
Referring to FIG. 1, a diagram depicts a portion of a program stack in memory in which several stack frames are allocated. The stack in FIG. 1 xe2x80x9cgrows downwardxe2x80x9d from a high memory address to a low memory address each time a stack frame is added in response to a procedure call. A Current Stack Frame is associated with the last called function. It is to be understood that the stack frame structures depicted in FIG. 1 are, in general, exemplary of conventional structures that are well-known in the art. In general, a frame typically comprises data blocks for storing the following pieces of information:
a function return address: the instruction to be executed after the called function completes execution;
a previous (old) frame pointer: this is the frame pointer of the calling function;
parameters: the arguments that are passed by the calling function to the called function;
local variables: this is where the state specific to the function is stored; and
a frame pointer (FP) or local base (LB) pointer: this pointer points to a fixed location in the frame (e.g., in FIG. 1, the FP is used to identify the base (beginning) of the current stack frame). Because the FP points to a fixed location, it may be used to identify the address of the local variables.
By way of example in FIG. 1, conceptually, the first variable (Local Var1) for the current function is at address (Frame Pointer+offset1), and the second variable (Local Var2) is at (Frame Pointer+offset2). In addition, in the illustrative embodiment of FIG. 1, the Frame Pointer points to the address of the Old Frame Pointer of the previous stack frame associated with the calling function (although, in general, the FP plus some offset points to the old frame (the offset in FIG. 1 has a value of 0)). This mechanism allows what is known as xe2x80x9cfollowing the back chainxe2x80x9d to find the beginning of any previous stack frame on the stack.
A xe2x80x9ccalling sequencexe2x80x9d refers to the instructions that are required to call a function and pass it parameters. During execution of the calling sequence, a stack frame is generated and xe2x80x9cpushedxe2x80x9d onto the stack for the called function. Calling sequences and stack frame organizations differ from operating system to operating system. In general, a typical calling sequence comprises the following steps. First, the calling function will push all arguments on the stack (i.e., pass the parameters to the called function). Next, the xe2x80x9creturn addressxe2x80x9d is pushed onto the stack and then and the program xe2x80x9cjumpsxe2x80x9d to the new routine (called function). Next, the current FP pointer is pushed onto to the stack in the memory location after the xe2x80x9creturn addressxe2x80x9d (i.e., this saves the current FP as the xe2x80x9cOld FPxe2x80x9d so that it can be restored at procedure exit). The FP is set to the current stack address (i.e., the stack pointer is copied into FP to create the new (current) FP). Finally, the stack pointer is incremented to reserve the space needed to store the local variables of the called function.
A corresponding return sequence comprises the following steps. First, the stack pointer is set to the value of current FP. The next steps are to pop stack into frame pointer, pop stack, and then jump to top of stack value.
FIG. 1 illustrates a Current Stack Frame as comprising the memory locations from the Frame Pointer to the Stack Pointer (which points to the top of the stack). In addition, a Previous Stack Frame comprises the memory locations beginning from Old Frame Pointer2 and ending at Return Address1. It is assumed that the function associated with the Previous Stack Frame is a xe2x80x9ccalling functionxe2x80x9d that calls the function (a xe2x80x9ccalled functionxe2x80x9d) associated with the Current Stack Frame. It is further assumed that parameters Arg1 and Arg2 are the parameters that are passed to the called function from the calling function. Although Arg1, Arg2 and Return Addressl are shown as being part of the Previous Stack Frame of the calling function for purposes of illustration, it is to be understood that other conventions consider such values as being elements of the Current Stack Frame.
Referring now to FIG. 2, a diagram illustrates a stack frame structure for the known AIX platform. AIX is an open operating system developed by International Business Machines (IBM) Corporation that is based on a version of UNIX. The AIX stack frame structure differs, for instance, from the stack frame structure of FIG. 1 in that it dispenses with a frame pointer, basing everything off a Stack Pointer (in some special cases, however AIX will use a frame pointer). As shown in FIG. 2, in AIX, stacks grow downwards (i.e. the Stack Pointer decreases as new frames are created). Furthermore, in AIX, arrays typically grow upwards. For instance, as shown in FIG. 2, an Array Pointer is incremented as larger indexed elements of an array, Array Var[1] . . . Array Var[n], are accessed. The Stack Pointer points to the memory location at the top of a Current Frame associated with the procedure being executed. This memory location contains a Back Chain Pointer2 which points to a memory location at the top of the previous stack frame of the calling procedure (which memory location contains a Back Chain Pointer1 that points to the top of its calling procedure, and so on). The Back Chain Pointers provide the mechanism for xe2x80x9cfollowing the back chain.xe2x80x9d The back chain pointer (not shown) of the first procedure in the program has a value of 0.
Furthermore, a Procedure Return Pointer1 contains the address (in the calling procedure) to which the called current procedure must return after it completes execution. In particular, when the called procedure completes, the Stack Pointer is set to the top of the calling procedure by reading the Back Chain Pointer2. The Procedure Return Pointer1 is then read and the program branches to this address.
The overflow of a stack allocated array (or buffer) can potentially lead to what is known as a xe2x80x9cStack Smashing Attack.xe2x80x9d Buffer overflow occurs when incorrect programming allows a user of a program to write beyond the bounds of some array (buffer). This can occur, for example, when the programmer expects the user to input no more than N characters of input and allocates an array of size N, but does not add any code to prevent the user from inputting more than N characters. In that case a user entering more than N characters will write beyond the bounds of the array into adjacent memory. If the buffer that overflows was part of the stack, the overflow will overwrite the portions of the stack adjacent to the buffer. Further, if the overflow is large enough, the function return address of some stack frame will be overwritten. Eventually, when the function for that stack returns, instead of returning to the correct address, it will return to an address determined by the overflow. This chain of events may be used by a hacker to perform what is known as xe2x80x9cstack smashing.xe2x80x9d
By way of example with reference to FIG. 1, it is assumed that the value of Arg1 that is passed to the called function is a pointer that points to a stack allocated array, Local VarB[1] . . . Local VarB[n], that is located within the Previous Stack Frame associated with the calling function. Depending on the direction of the array growth (in FIG. 1, the array is shown as growing in either direction), the overflow of the array can lead to overwriting either Return Address1 or Old Frame Pointer2 of the Previous Stack Frame and/or overwriting Return Address2 of the stack frame previous to the Previous Stack Frame.
In addition, with reference to FIG. 2, the Current Frame is shown having an array, Array Var[1] . . . Array Var[n], which grows upward. If the calling procedure, or more typically, some procedure it calls, writes beyond this pointer, it will eventually overwrite both the Back Chain Pointer1 and the Procedure Return Pointer1. Now, when the procedure returns, the Stack Pointer will be set to some unanticipated location, and the program will branch to some unanticipated location.
Stack smashing allows a malicious user (xe2x80x9cattackerxe2x80x9d) to break security, and obtain privileged access. A typical stack smashing process consists of the following steps:
the attacker identifies a privileged program that contains a potential buffer overflow;
the attacker then proceeds to input into the buffer a string that is actually executable binary code native to the machine being attacked, that invokes some restricted action, the xe2x80x9cattack codexe2x80x9d;
the attacker continues to input into the buffer until the buffer overflows into some function return pointer and sets that pointer to the start of the attack code; and
the privileged program then (eventually) returns from the function whose return pointer was overwritten, and starts executing code invoking the restricted action. Since the program is a privileged program, the restricted action is executed. Thus, a buffer overflow in a privileged program allows the attacker to perform restricted actions that would otherwise be forbidden to him. This attack is variously known as a xe2x80x9cbuffer overrunxe2x80x9d or xe2x80x9cstack smashingxe2x80x9d attack.
There have many techniques developed to prevent buffer overrun and stack smashing attacks. For instance, one method involves writing a compiler that will compile a C program so that pointers carry bounds information with them. This method has several disadvantages. For instance, this method requires the applications and libraries to be recompiled with the safe compiler. In addition, the sizes of the pointers typically double. Furthermore, while some safe compilers can handle all strictly compliant ANSI C programs, they break down on various non-compliant idioms.
Another approach is to make the stack segments non-executable. This requires operating system intervention, but with the appropriate operating system support should offer a viable solution.
Yet another approach is one in which the compiler puts a xe2x80x9ccanaryxe2x80x9d word just before the procedure return pointer on the stack. A canary word is simply a word containing a special pattern. Prior to returning from a routine, the code determines if the word has been overwritten. If so, it is determined that there has been a buffer overrun. Apart from requiring recompilation, this technique also suffers from the problem that it can be defeated by, e.g., guessing the canary word.
Accordingly, there is a need for a simplified, yet powerful and efficient, method that allows a called function to ascertain a upper limit to the amount of data that can be written to a stack allocated array/buffer so as to prevent back chain and/or procedure return pointers from potentially being overwritten due to array/buffer overrun.
The present invention is directed to a method that allows a called procedure to determine a xe2x80x9csafexe2x80x9d upper bound value representing the amount of data that can be written to a stack allocated array/buffer without overwriting any stack-defined data stored in reserved memory blocks within the stack (i.e., any region in memory that is preserved by a calling sequence). More specifically, when a called procedure is passed a stack allocated array/buffer as an argument, the method of the present invention allows the called procedure to call a xe2x80x9cbounds checkingxe2x80x9d procedure that calculates and returns the xe2x80x9csafexe2x80x9d upper bound value, thereby allowing the called procedure to, e.g., prevent a procedure return value from being overwritten due to array overflow when writing data to the array.
In one aspect of the present invention, a method for providing bounds checking on the size of input data being stored in an array comprises the steps of: determining if the array is located on a program stack; determining a boundary value representing a maximum amount of data that can be written to the array without overwriting a predefined region in the program stack, if the array is determined to be on the program stack; and writing data to the array based on the determined boundary value.
In another aspect of the present invention, the predefined region comprises a memory location that is preserved by a calling sequence to store, e.g., a procedure return pointer.
In yet another aspect of the invention, the step of determining a boundary value of the array comprises the steps of following the back chain pointers of stack frames on the stack to locate a stack frame containing the array and then, depending on the direction of the growth of the array, calculating the distance between the beginning of the array and the closest predefined region in the program stack. Depending on the given stack structure, the closest predefined region can be, for instance, the beginning or end location of the stack frame containing the array.
Advantageously, the present invention may readily be implemented in any operating system/library to provide secure implementations of library functions that have buffer overflow vulnerabilities.
These and other aspects, features, and advantages of the present invention will become apparent from the following detailed description of the preferred embodiments, which is to be read in connection with the accompanying drawings.